GATE PYQ

GATE CSE 2006

Q21.
A CPU has five-stages pipeline and runs at 1GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 10^{9} instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, then total execution time of the program is

Q22.
The atomic feth-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x . Consider the following implementation of P and V functions on a binary semaphore S. void P(binary_semaphoreS){ unsigned y; unsignedx =& (S->value); do { fetch-and-set x,y; } while(y); } void V (binary_semphore*S){ S_>value = 0; } Which one of the following is true?

Q23.
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left. void barrier (void) { 1: P(S); 2: process_arrived++; 3. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally. The above implementation of barrier is incorrect. Which one of the following is true?

Q24.
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left. void barrier (void) { 1: P(S); 2: process_arrived++; 3. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.Which one of the following rectifies the problem in the implementation?

Q25.
Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened.

Q26.
Consider the following propositional statements: P1:((A\wedge B)\rightarrow C)\equiv (A\rightarrow C)\wedge (B\rightarrow C) P2:((A\vee B)\rightarrow C)\equiv (A\rightarrow C)\vee (B\rightarrow C) Which one of the following is true?

Q27.
An implementation of a queue Q, using two stacks S1 and S2, is given below: void insert(Q,x){ push (S1,x); } void delete(Q, x){ if (stack-empty (S2))then if (stack-empty (S1))then{ print("Q is empty"); return; } else while (! (stack-empty)(S1)){ x=pop(S1); push(S2,x); } x=pop(S2); } Let n insert and m(\leqn) delete operations be performed in an arbitrary on an empty queue Q, Let x and y be the number of push and pop operations performed respectively in the processes. Which one of the following is true for all m and n ?

Q28.
Consider the following recurrence: T(n)=2T(\left \lceil \sqrt{n} \right \rceil)+ 1, T(1) = 1 Which one of the following is true?

Q29.
Let L1 be regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Q30.
If s is a string over (0+1)*, then let n_0 (s) denote the number of 0's in s and n_1 (s) the number of 1's in s. Which one of the following languages is not regular?